//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,2,1]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：head = [1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围[1, 105] 内 
// 0 <= Node.val <= 9 
// 
//
// 
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 栈 递归 链表 双指针 
// 👍 1254 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.Stack;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution234 {
    /**
     * 解题思路：
     * 1. 获取链表的中间指针
     * 2. 中间指针往后开始插入栈（后进先出)
     * 3. 在链表开始与栈顶元素比较，完全匹配则为true
     *
     * 解答成功:
     * 			执行耗时:25 ms,击败了5.20% 的Java用户
     * 			内存消耗:55.8 MB,击败了15.61% 的Java用户
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        // 获取中间指针
        ListNode mid = head;
        ListNode last = head;
        while(last != null && last.next != null) {
            mid = mid.next;
            last = last.next.next;
        }

        // 将中间指针（含）开始的元素放入栈中
        Stack<ListNode> stack = new Stack<>();
        while(mid != null){
            stack.push(mid);
            mid = mid.next;
        }

        // 遍历链表，匹配栈，匹配到则出栈，直到栈为空
        while (!stack.isEmpty()) {
            if(head.val == stack.peek().val) {
                stack.pop();
                head = head.next;
                continue;
            }
            // 如果栈还存在元素时，链表就匹配不到栈顶了，则说明不是回文链表，返回false;
            return false;
        }

        return true;
    }


    /**
     * 解题思路
     * 1.获取链表的中间指针
     * 2.对中间指针往后的链表进行反转
     * 3.对比链表和反转后链表 完全一致返回true
     *
     * 	解答成功:
     * 			执行耗时:5 ms,击败了65.77% 的Java用户
     * 			内存消耗:51.4 MB,击败了34.17% 的Java用户
     * @param head
     * @return
     */
    public boolean isPalindromeAnswer(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode listNode11 = new ListNode(1);
        ListNode listNode12 = new ListNode(2);
        ListNode listNode13 = new ListNode(2);
        ListNode listNode14 = new ListNode(1);
//        ListNode listNode15 = new ListNode(5);
//        listNode14.next = listNode15;
        listNode13.next = listNode14;
        listNode12.next = listNode13;
        listNode11.next = listNode12;

        new Solution234().isPalindrome(listNode11);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
